/*
 * @lc app=leetcode.cn id=39 lang=javascript
 *
 * [39] 组合总和
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  let res = [];
  let dfs = function (diff, nums, index) {
    if (diff == 0) {
      res.push(nums);
      return;
    }
    if (diff < 0) {
      return;
    }
    for (let i = index; i < candidates.length; i++) {
      if (candidates[i] <= diff) {
        let arr = nums.slice();
        arr.push(candidates[i]);
        dfs(diff- candidates[i] , arr, i);
      }
    }
  };
  dfs(target,[],0);
  return res
};
// @lc code=end
console.log(combinationSum([1, 2, 3, 4], 5));
var combinationSum = function (candidates, target) {
  let res = [];
  let hash = new Set();
  let db = function (target, sum, nums) {
    if (sum == target) {
      if (!hash.has(nums.sort().toString())) {
        res.push(nums);
        hash.add(nums.sort().toString());
        return;
      }
    }
    if (sum > target) {
      return;
    }
    for (let i = 0; i < candidates.length; i++) {
      if (candidates[i] <= target) {
        let temp = sum + candidates[i];
        let copy = nums.slice();
        copy.push(candidates[i]);
        db(target, temp, copy);
      }
    }
  };
  db(target, 0, []);
  return res;
}; //垃圾解法
var combinationSum = function(candidates, target) {
    const ans = [];
    const dfs = (target, combine, idx) => {
        if (idx === candidates.length) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        // 直接跳过
        dfs(target, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
        }
    }

    dfs(target, [], 0);
    return ans;
};//正规解法